package com.example.sword;

import java.util.ArrayList;

public class Test4 {

    public static void main(String[] args) {
        System.out.println(11111);
    }


    public class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;

        TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树
     */

//    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//        if (pre.length==0)return null;
//        TreeNode root;
//
//        for (int i = 0; i < in.length; i++) {
//            if (in[i]==pre[0]){
//                root = new TreeNode(pre[0]);
//                root.left = reConstructBinaryTree()
//            }
//        }
//    }

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root==null){
            return result;
        }
        serch(root,0,new ArrayList<Integer>(),target,result);
        return result;
    }

    //和为某值的路径
    private void serch(TreeNode node, int sum, ArrayList<Integer> list, int target, ArrayList<ArrayList<Integer>> result) {

        if (sum==target&&!result.contains(list)){
            result.add(list);
            return;
        }

        if (node==null){
            return;
        }

        sum = sum+node.val;
        list.add(node.val);
        if (sum>target)
            return;

        serch(node.left,sum,new ArrayList<>(list),target,result);
        serch(node.right,sum,new ArrayList<>(list),target,result);

    }

}
